#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define MAXN 505
#define MAXM 100005
using namespace std;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int n;
int grid[MAXN][MAXN];
bool visited[MAXN][MAXN];

int dfs(int i, int j, int d){
    if (visited[i][j]) return 0;

    visited[i][j] = true;
    int count = 1;
    for (int dir=0;dir<4;dir++){
        int i1 = i + dx[dir];
        int j1 = j + dy[dir];
        if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < n &&
            abs(grid[i1][j1]-grid[i][j]) <= d){
                count += dfs(i1,j1,d);
        }
    }
    return count;
}

bool is_possible(int d){
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
        visited[i][j] = false;

    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
        if (!visited[i][j]){
            if (dfs(i,j,d) * 2 >= n*n){
                return true;
            }
        }
    return false;
}

int main()
{
    freopen("tractor.txt","r", stdin);
    scanf("%d", &n);
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            scanf("%d", &grid[i][j]);
        }
    }
    int lo = -1, hi = 1000000;
    while (hi > lo + 1){
        int mid = (lo+hi)/2;
        if (is_possible(mid)){
            hi = mid;
        } else {
            lo = mid;
        }
    }
    printf("%d\n", hi);
    return 0;
}
